10080. Сурок 2
Имеются n сурков и m нор,
заданные уникальными координатами (x,
y). Ястреб съест сурка, если тот не
спрячется в нору в течение s секунд.
Все сурки имеют одинаковую скорость передвижения v. В каждой норе может спрятаться не более одного сурка. Суркам
следует разработать стратегию, согласно которой они рассредоточатся по норам.
При этом число доступных ястребу сурков через s секунд должно быть минимально. Определить наименьшее число
сурков, которое не сможет спрятаться от ястреба.
Вход. Состоит
из нескольких тестов. Первая строка каждого теста содержит четыре натуральных
числа n, m, s, v. Следующие n строк описывают координаты сурков, за которыми идут m строк с координатами нор.
Выход. Для каждого теста вывести
наименьшее число сурков, которое не сможет спрятаться от ястреба.
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0
Пример выхода
1
паросочетание
Построим двудольный граф, вершины
одной доли соответствуют суркам, а второй доли – норам. От каждого сурка ведем
ребро к норе, если он может спрятаться в ней (это возможно если расстояние
между сурком и норой не больше sv).
Строим матрицу смежности g, в которой
индексы от 1 до n соответствуют
суркам, а индексы от n + 1 до n + m
норам. Таким образом, если i - ый
сурок может добежать за отведенное время s
до j - ой норы, то устанавливаем g[i][n+j] = 1. .При решении задачи о паросочетании
следует создать мнимые вершины – исток (нулевая вершина) и сток (вершина с
номером n + m + 1). Для этого устанавливаем g[0][i] = 1 для всех 1 £ i £ n и g[n+i][n+m+1] = 1 для 1 £ i £ m, так как из
нулевой вершины ребра ведут к суркам, а из каждой норы ребро ведет в n + m
+ 1 - ую вершину. Пропускную способность всех ребер считаем равной 1. Ищем
величину максимального потока MaxFlow
от нулевой вершины до n + m + 1 - ой, получая максимальное
количество сурков, которое может спрятаться от ястреба. Соответственно
наименьшее число сурков, которое не сможет спрятаться от ястреба, равно n – MaxFlow.
Двумерный массив g размером 202 *
202 хранит матрицу пропускных способностей графа (она же матрица смежности).
Массивы gopher и hole хранят координаты начального положения сурков и нор.
#define MAX 101
int g[2*MAX][2*MAX], used[2*MAX];
double gopher[MAX][2], hole[MAX][2];
Функция aug ищет дополняющий
путь.
int aug(int
x,int t,int
CurFlow)
{
if (x == t) return CurFlow;
if
(used[x]++) return 0;
for (int Flow,y = 0; y <= n+m+1; y++)
{
if (g[x][y]
> 0 && (Flow = aug(y,t,min(CurFlow,g[x][y]))))
{
g[x][y] -= Flow; g[y][x] += Flow;
return
Flow;
}
}
return 0;
}
Основной цикл программы. Читаем
координаты местоположения сурков и нор в массивы gopher и hole. Квадрат
максимального расстояния, которое могут пробежать сурки, будучи не пойманными
ястребом, равен dist = (sv)2.
int MaxFlow, flow;
while(scanf("%d
%d %d %d",&n,&m,&s,&v) == 4)
{
for(i = 1; i
<= n; i++) scanf("%lf %lf",&gopher[i][0],&gopher[i][1]);
for(i = 1; i
<= m; i++) scanf("%lf %lf",&hole[i][0],&hole[i][1]);
dist = s * v * s * v;
memset(g,0,sizeof(g));
Вычисление расстояний между
сурками и норами. Заполнение массива g.
for(i = 1; i
<= n; i++)
for(j = 1; j
<= m; j++)
{
temp = (hole[j][0] - gopher[i][0]) *
(hole[j][0] - gopher[i][0]) +
(hole[j][1] -
gopher[i][1]) * (hole[j][1] - gopher[i][1]);
if (temp
<= dist) g[i][n+j] = 1;
}
Установка ребер, исходящих из
нулевой вершины и ребер, входящих в n
+ m + 1 - ую.
for(i = 1; i
<= n; i++) g[0][i] = 1;
for(i = 1; i <= m; i++) g[n+i][n+m+1]
= 1;
Поиск максимального паросочетания
MaxFlow.
MaxFlow = 0;
do
{
memset(used,0,sizeof(used));
} while
((flow = aug(0,n+m+1,0x7FFFFFFF)) && (MaxFlow += flow));
Вывод наименьшего числа сурков,
которое не сможет спрятаться от ястреба. Оно равно n – MaxFlow.
printf("%d\n",n - MaxFlow);
}